package com.github.yangyishe;

import java.util.*;

/**
 * 909. 蛇梯棋
 * https://leetcode.cn/problems/snakes-and-ladders/?envType=study-plan-v2&envId=top-interview-150
 * 虽然不是最快, 但思想和较快的思想是比较一致的.只是因为用到了map所以比较慢.
 *
 * 给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。
 *
 * 玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。
 *
 * 每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：
 *
 * 选定目标方格 next ，目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)] 。
 * 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
 * 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
 * 当玩家到达编号 n2 的方格时，游戏结束。
 * r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。
 *
 * 注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。
 *
 * 举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。
 * 返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
 * 输出：4
 * 解释：
 * 首先，从方格 1 [第 5 行，第 0 列] 开始。
 * 先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。
 * 然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。
 * 接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。
 * 最后决定移动到方格 36 , 游戏结束。
 * 可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。
 * 示例 2：
 *
 * 输入：board = [[-1,-1],[-1,3]]
 * 输出：1
 *
 *
 * 提示：
 *
 * n == board.length == board[i].length
 * 2 <= n <= 20
 * grid[i][j] 的值是 -1 或在范围 [1, n2] 内
 * 编号为 1 和 n2 的方格上没有蛇或梯子
 */
public class Problem909 {
    public static void main(String[] args) {
        int[][] board=new int[][]{
                {-1,-1,-1,-1,48,5,-1},
                {12,29,13,9,-1,2,32},
                {-1,-1,21,7,-1,12,49},
                {42,37,21,40,-1,22,12},
                {42,-1,2,-1,-1,-1,6},
                {39,-1,35,-1,-1,39,-1},
                {-1,36,-1,-1,-1,-1,5}
        };
        Problem909 problem909 = new Problem909();
//        Map<Integer, Integer> bridgeMap = problem909.convertBridgeMap(board);
//        System.out.println(bridgeMap);


        int i = problem909.snakesAndLadders(board);
        System.out.println(i);

    }

    /**
     * 思路:
     * 贪心算法可能获得能否移动到最后, 但无法获取到最小步数.
     * 另一种思路是逆序思考, 任意一个点的前置点通常会有多个, 找到其中最小的那个点, 逐次找, 直到从1开始. 但改法也无法保证步数最小.
     * 可能只有遍历所有的蛇桥分支才可以.
     *
     * 另: 本体的n*n看起来并无影响实际思路之必要, 即使将之看做一条线也可以.
     *
     * @param board
     * @return
     */
    public int snakesAndLadders(int[][] board) {
        Map<Integer, Integer> bridgeMap = convertBridgeMap(board);
        int minStep = minStep(1, board.length * board.length, bridgeMap,new HashSet<>());

        return minStep==Integer.MAX_VALUE?-1:minStep;
    }

    /**
     * 假定
     * @param start
     * @param bridgeMap
     * @return
     */
    private int minStep(int start,int target, Map<Integer,Integer> bridgeMap,Set<Integer> usedStepSet){
        if(bridgeMap.get(target)!=null){
            return Integer.MAX_VALUE;
        }
        if(target==start){
            return 0;
        }
        if(target-start<=6){
            return 1;
        }

        System.out.println("step:"+start+","+usedStepSet);
        // 高效的选择(自动筛除低效选择)
        Set<Integer> effChoice=new HashSet<>();
        Set<Integer> cloneUsedSet=new HashSet<>(usedStepSet);
        for(int i=1;i<=6;i++){
            Integer bridgeStep = bridgeMap.get(start + i);
            if(bridgeStep !=null){
                // 仅记录桥,不记录蛇->此处为缺陷,通过蛇不一定不是最短路径->通过是否走过来判定
                if(!usedStepSet.contains(bridgeStep)){
                    effChoice.add(bridgeStep);
                    cloneUsedSet.add(bridgeStep);
                }
            }else{
                effChoice.add(start+i);
                cloneUsedSet.add(start+i);
                effChoice.remove(start+i-1);
            }
        }

        if(effChoice.size()==0){
            return Integer.MAX_VALUE;
        }
        int minStep=Integer.MAX_VALUE;
        for(int choice:effChoice){
            minStep=Math.min(minStep,minStep(choice,target,bridgeMap,cloneUsedSet));
        }

        return minStep==Integer.MAX_VALUE?Integer.MAX_VALUE:minStep+1;
    }

    /**
     * 转换为稀疏数组
     * @param board
     * @return
     */
    private Map<Integer,Integer> convertBridgeMap(int[][] board){
        int n=board.length;
        int csum=0;
        int rsum;
        Map<Integer,Integer> bridgeMap=new HashMap<>();
        // 遍历方式:从左下角开始遍历
        for(int r=n-1;r>=0;r--){
            rsum=0;
            if((n-1-r)%2==0){
                for(int c=0;c<n;c++){
                    rsum++;
                    if(board[r][c]!=-1){
                        bridgeMap.put(csum+rsum,board[r][c]);
                    }
                }
            }else{
                for(int c=n-1;c>=0;c--){
                    rsum++;
                    if(board[r][c]!=-1){
                        bridgeMap.put(csum+rsum,board[r][c]);
                    }
                }
            }

            csum+=n;
        }

        return bridgeMap;
    }
}
